package com.xxd.algo.leetcode.base;

/**
 * @author: XiaoDong.Xie
 * @create: 2020-07-03 16:33
 * @description:
 */
public class Offer51_ReversePairs {
    public int reversePairs(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }

        return mergeSort(arr, 0, arr.length - 1);
    }

    /**
     * mergeSort 就是一直切割，在整体逻辑处理
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private int mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }

        int mid = l + ((r - l) >> 1);
        return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    /**
     * merge 过程
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     * @return
     */
    private int merge(int[] arr, int l, int mid, int r) {
        int count = 0;
        int[] help = new int[r - l + 1];

        int p1 = l;
        int p2 = mid + 1;
        int i = 0;
        while (p1 <= mid && p2 <= r) {
            count += arr[p1] > arr[p2] ? (mid - p1 + 1) : 0;
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }

        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }

        return count;
    }

    public static void main(String[] args) {
        //int[] arr = {7, 3, 4, 2, 5, 9};
        int[] arr = {1, 3, 2, 3, 1};
        Offer51_ReversePairs offer51_reversePairs = new Offer51_ReversePairs();
        System.out.println(offer51_reversePairs.reversePairs(arr));
    }
}
